public class BinaryHeap implements PriorityQueue {

	private static final int DEFAULT_CAPACITY = 10;
	
	private Comparable[] items;
	private int size;


	public BinaryHeap() {
		init( DEFAULT_CAPACITY );
	}


	public BinaryHeap( int capacity ) {
		if ( capacity < 0 ) {
			throw new IllegalArgumentException();
		}
		init( capacity );
	}


	private void init( int capacity ) {
		items = new Comparable[ capacity + 1 ];
		size = 0;
	}


	public BinaryHeap( Comparable[] arr ) {
		items = new Comparable[ arr.length + 1 ];

		for ( int i = 0; i < arr.length; ++i ) {
			items[ i+1 ] = arr[ i ];
		}

		size = arr.length;

		buildHeap();	
	}


	private void buildHeap() {
		for ( int i = size / 2; i > 0; --i ) {
			percolateDown( i );
		}
	}


	private void grow() {
		Comparable[] newItems = new Comparable[ items.length * 2 ];
		for ( int i = 0; i < items.length; ++i ) {
			newItems[ i ] = items[ i ];
		}
		items = newItems;
	}
	

    public void insert( Comparable x ) {
		if ( size + 1 == items.length ) {
			grow();
		}

		items[ ++size ] = x;
		percolateUp( size );
	}


	private void percolateUp( int i ) {
		if ( i > 1 && items[i].compareTo(items[i/2]) < 0 ) {
			swap( i, i/2 );
			percolateUp( i/2 );
		}
	}


	private void swap( int i, int j ) {
		Comparable tmp = items[ i ];
		items[ i ] = items[ j ];
		items[ j ] = tmp;
	}


    public Comparable findMin( ) {
		if ( isEmpty() ) {
			throw new IllegalStateException();
		}

		return items[ 1 ];
	}


    public Comparable deleteMin( ) {
		if ( isEmpty() ) {
			throw new IllegalStateException();
		}
		
		Comparable min = items[ 1 ];
		items[ 1 ] = items[ size ];
		items[ size ] = null;
		--size;
		
		percolateDown( 1 );
		
		return min;
	}


	private void percolateDown( int i ) {
		int child = i * 2;
		
		if ( child < size && items[child+1].compareTo(items[child]) < 0 ) {
			++child;
		}
		
		if ( child <= size && items[i].compareTo(items[child]) > 0 ) {
			swap( i, child );
			percolateDown( child );
		}
	}


    public boolean isEmpty( ) {
		return size == 0;
	}


    public void makeEmpty( ) {
		init( DEFAULT_CAPACITY );
	}
    

    public int size( ) {
		return size;
	}

}